package 背包;

import java.util.Scanner;

public class test {
    // 01背包: 所有物品都只有一个 --> 基础问题
    // 1. 背包不一定装满
    // dp[i][j]: 表示从前i个物品中进行挑选,总体积不超过j,所有选法中,能选出来的最大值
    // 根据最后一步的状况,分情况讨论(1.不选i物品 --> dp[i-1][j];2.选i物品 --> w[i]+dp[i-1][j-v[i]])

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); // 物品数量
        int v = in.nextInt(); // 背包体积
        int[] N = new int[n];
        int[] V = new int[n];
        for (int i = 0; i < n; i++) {
            N[i] = in.nextInt(); //价值
            V[i] = in.nextInt(); //体积
        }
        // 问题1:不要求装满背包，求能获得的最大总价值
        System.out.println(getResult1(N,V,v));
    }

    public static int getResult1(int[] N,int[] V,int v){
        int n = N.length; // 物品个数
        int[][] dp = new int[n+1][n+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= v; j++) {
                dp[i][j] = dp[i-1][j];
                if(j>=V[i]&&dp[i-1][j]-V[i]!=-1)
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-V[i]]+N[i]);
            }
        }
        return dp[n][v];
    }
}
